/* /////////////////////////////////////////////////////////////////////////////
 * File:        NaiveQuery.d
 *
 * Purpose:     何も工夫しない方法でクエリを実現する
 *
 * Created      9th June 2007
 * Updated:     13th June 2007
 *
 * www:         http://
 *
 * Copyright (C) 2007 by Yasunobu Imamura
 *
 * This software is provided 'as-is', without any express or implied warranty.
 * In no event will the authors be held liable for any damages arising from the
 * use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not claim
 * that you wrote the original software. If you use this software in a product,
 * an acknowledgment in the product documentation would be appreciated but is
 * not required.
 *
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 *
 * 3. This notice may not be removed or altered from any source distribution. 
 *
 * ////////////////////////////////////////////////////////////////////////// */

module gtree.NaiveQuery;

private import std.stdio;

class NaiveQuery(T)
{
	struct pair
	{
		T.DistanceType d;
		T t;
	}

	pair[] ranking;
	int k;
	T.DistanceType r;
	T q;

	this(T q2, T.DistanceType r2, int k2)
	{
		q = q2;
		r = r2;
		k = k2;

		//予め使うメモリを確保しておく
		ranking = new pair[k2 + 1];
		ranking.length = 0;
	}

	void print()
	{
		int i = 0;
		int j = 1;
		T.DistanceType d;
		foreach(a; ranking)
		{
			++i;
			if(i==1 || a.d!=d)
			{
				d = a.d;
				j = i;
			}
			writefln
			(
				"result",
				i,
				"(",
				j,
				"): \"",
				a.t.data,
				"\", ",
				a.d
			);
		}
	}

	void push(T o)
	{
		T.DistanceType d = q.distance(o);
		if(r<d)
			return;

		//新しい結果をソート挿入する
		int i = ranking.length - 1;
		ranking.length = ranking.length + 1;
		while(0<=i)
		{
			if(ranking[i].d<=d)
				break;
			ranking[i+1] = ranking[i];
			--i;
		}
		ranking[i+1].d = d;
		ranking[i+1].t = o;
		//ranking[i+1] = pair(d, o);

		//上位k個で結果を打ち切る
		if(k<ranking.length)
		{
			ranking.length = k;
		}

		//新しい範囲の設定
		if(k==ranking.length)
		{
			r = ranking[$ - 1].d;
		}
	}

	T GetObject(int n)
	{
		if(0<=n && n<ranking.length)
		{
			return ranking[n].t;
		}
	}

	T.DistanceType getDistance(int n)
	{
		if(0<=n && n<ranking.length)
		{
			return ranking[n].d;
		}
	}
}
